Listonosze

Limit pamięci: 64 MB

We wsi Bajtoły Dolne wybudowano piękny i nowy Urząd Pocztowy. Zatrudniono dwóch listonoszy, którzy co dzień rano będą wyruszać z budynku poczty i rozwozić listy po wsi. Należy tak zaplanować ich trasy, by ostatni list został doręczony jak najwcześniej.

W Bajtołach jest domów ponumerowanych liczbami całkowitymi od 1 do . Budynek poczty jest domem z numerem 1. Domy są połączone spójną siecią dwukierunkowych dróg. Przejechanie odcinka drogi zajmuje listonoszowi jedną minutę.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita oznaczająca liczbę domów we wsi (). W kolejnych wierszach znajdują się opisy dróg. Każdy z nich składa się z dwóch liczb oznaczających drogę łączącą domy i ().

Wyjście

W jedynym wierszu wyjścia należy wypisać minimalny czas w minutach, w którym listonoszom uda się rozwieźć wszystkie listy.

Przykład

Dla danych wejściowych:

6
1 2
2 3
5 2
3 4
6 1

poprawną odpowiedzią jest:

4

Autor zadania: Tomasz Idziaszek.